/*
 * @Author: Tendo 
 * @Date: 2021-11-06 11:44:34 
 * @Last Modified by: Tendo
 * @Last Modified time: 2021-11-06 11:47:42
 */
/**
 * @param {number} k
 * @param {number} n
 * @return {number[][]}
 */
let res = [],
    path = [];
var combinationSum3 = function (k, n) {
    res = []
    dfs(n, k, 0, 1)
    return res
};
const dfs = (targetSum, k, sum, startIndex) => {
    if (sum > targetSum) { // 剪枝操作
        return; // 如果path.length == k 但sum != targetSum 直接返回
    }
    // 所以如果path.length 和 k相等了，就终止。
    // 如果此时path里收集到的元素和（sum） 和targetSum（就是题目描述的n）相同了，就用result收集当前的结果。
    if (path.length === k) {
        if (sum === targetSum) {
            res.push([...path])
        }
        return // 如果path.length == k 但sum != targetSum 直接返回
    }
    for (let i = startIndex; i <= 9; i++) {
        sum += i
        path.push(i);
        dfs(targetSum, k, sum, i + 1); // 递归 注意i+1调整startIndex
        sum -= i; // 回溯
        path.pop(); // 回溯
    }
}
